// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem16.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=16 lang=cpp
 *
 * [16] 最接近的三数之和
 */

// @lc code=start
class Solution {
public:
    /* 暴力解法
    int threeSumClosest(vector<int>& nums, int target) {
        int size = nums.size();
        int min_abs = INT_MAX;
        int min_sum = 0;
        for(int i = 0 ; i < size ; i++)
        {
            for(int j = i + 1;j < size ; j++)
            {
                for(int k = j + 1;k < size; k++)
                {
                    int temp = nums[i]+nums[j]+nums[k];
                    int temp_abs = abs(target-temp);
                    if(temp_abs < min_abs)
                    {
                        min_sum = temp;
                        min_abs = temp_abs;
                    }
                }
            }
        }
        return min_sum;
    }
    */

    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        int size = nums.size();
        int left = 0;
        int right = size - 1;
        
        int min_abs = INT_MAX;
        int min_sum = 0;

        for(int i = 0 ; i < size ; i++)
        {
            left = i + 1;
            right = size - 1;
            while (left < right)
            {
                int temp_sum = nums[i] + nums[left] + nums[right];
                if(temp_sum == target)
                {
                    return temp_sum;
                }
                int temp_abs = abs(temp_sum - target);
                if(temp_abs < min_abs)
                {
                    min_abs = temp_abs;
                    min_sum = temp_sum;
                }
                if(temp_sum > target)
                {
                    right--;
                }
                else
                {
                    left++;
                }

            }
            
        }
        return min_sum;
    }
};
// @lc code=end

